The Debug-Info structure directly represents information about the source code, and points to other structures that describe the layout of run-time data structures.
Make some sort of minimal debug-info format that would support at least the common cases of level 1 (since that is what we would release), and perhaps level 0. Actually, it seems it wouldn't be hard to crunch nearly all of the debug-function structure and debug-info function map into a single byte-vector. We could have an uncrunch function that restored the current format. This would be used by the debugger, and also could be used by purify to delete parts of the debug-info even when the compiler dumps it in crunched form. [Note that this isn't terribly important if purify is smart about debug-info...] |#
Compiled source map representation:
[### store in debug-function PC at which env is properly initialized, i.e. args (and return-pc, etc.) in internal locations. This is where a :function-start breakpoint would break.]
[### Note that that we can easily cache the form-number => source-path or form-number => form translation using a vector indexed by form numbers that we build during a walk.]
Instead of using source paths in the debug-info, use "form numbers". The form number of a form is the number of forms that we walk to reach that form when doing a pre-order walk of the source form. [Might want to use a post-order walk, as that would more closely approximate evaluation order.]
We probably want to continue using source-paths in the compiler, since they are quick to compute and to get you to a particular form. [### But actually, I guess we don't have to precompute the source paths and annotate nodes with them: instead we could annotate the nodes with the actual original source form. Then if we wanted to find the location of that form, we could walk the root source form, looking that original form. But we might still need to enter all the forms in a hashtable so that we can tell during IR1 conversion that a given form appeared in the original source.]
Note that form numbers have an interesting property: it is quite efficient to determine whether an arbitrary form is a subform of some other form, since the form number of B will be > than A's number and < A's next sibling's number iff B is a subform of A.
This should be quite useful for doing the source=>pc mapping in the debugger, since that problem reduces to finding the subset of the known locations that are for subforms of the specified form.
Assume a byte vector with a standard variable-length integer format, something like this: 0..253 => the integer 254 => read next two bytes for integer 255 => read next four bytes for integer
Then a compiled debug block is just a sequence of variable-length integers in a particular order, something like this: number of successors ...offsets of each successor in the function's blocks vector... first PC [offset of first top-level form (in forms) (only if not component default)] form number of first source form first live mask (length in bytes determined by number of VARIABLES) ...more <PC, top-level form offset, form-number, live-set> tuples...
We determine the number of locations recorded in a block by the finding the start of the next compiled debug block in the blocks vector.
[### Actually, only need 2 bits for number of successors 0,1,2. We might want to use other bits in the first byte to indicate the kind of location.] [### We could support local packing by having a general concept of "alternate locations" instead of just regular and save locations. The location would have a bit indicating that there are alternate locations, in which case we read the number of alternate locations and then that many more SC-OFFSETs. In the debug-block, we would have a second bit mask with bits set for TNs that are in an alternate location. We then read a number for each such TN, with the value being interpreted as an index into the Location's alternate locations.]
It looks like using structures for the compiled-location-info is too bulky. Instead we need some packed binary representation.
First, let's represent a SC/offset pair with an "SC-Offset", which is an integer with the SC in the low 5 bits and the offset in the remaining bits: —————————————————- | Offset (as many bits as necessary) | SC (5 bits) | —————————————————- Probably the result should be constrained to fit in a fixnum, since it will be more efficient and gives more than enough possible offsets.
We can the represent a compiled location like this: single byte of boolean flags: uninterned name packaged name environment-live has distinct save location has ID (name not unique in this fun) name length in bytes (as var-length integer) ...name bytes... [if packaged, var-length integer that is package name length] ...package name bytes...] [If has ID, ID as var-length integer] SC-Offset of primary location (as var-length integer) [If has save SC, SC-Offset of save location (as var-length integer)]
But for a whizzy breakpoint facility, we would need a good source=>code map. Dumping a complete code=>source map might be as good a way as any to represent this, due to the one-to-many relationship between source and code locations.
We might be able to get away with just storing the source locations for the beginnings of blocks and maintaining a mapping from code ranges to blocks. This would be fine both for the profiler and for the "where am I running now" indication. Users might also be convinced that it was most interesting to break at block starts, but I don't really know how easily people could develop an understanding of basic blocks.
It could also be a bit tricky to map an arbitrary user-designated source location to some "closest" source location actually in the debug info. This problem probably exists to some degree even with a full source map, since some forms will never appear as the source of any node. It seems you might have to negotiate with the user. He would mouse something, and then you would highlight some source form that has a common prefix (i.e. is a prefix of the user path, or vice-versa.) If they aren't happy with the result, they could try something else. In some cases, the designated path might be a prefix of several paths. This ambiguity might be resolved by picking the shortest path or letting the user choose.
At the primitive level, I guess what this means is that the structure of source locations (i.e. source paths) must be known, and the source=>code operation should return a list of <source,code> pairs, rather than just a list of code locations. This allows the debugger to resolve the ambiguity however it wants.
I guess the formal definition of which source paths we would return is: All source paths in the debug info that have a maximal common prefix with the specified path. i.e. if several paths have the complete specified path as a prefix, we return them all. Otherwise, all paths with an equally large common prefix are returned: if the path with the most in common matches only the first three elements, then we return all paths that match in the first three elements. As a degenerate case (which probably shouldn't happen), if there is no path with anything in common, then we return *all* of the paths.
In the DEBUG-SOURCE structure we may ultimately want a vector of the start positions of each source form, since that would make it easier for the debugger to locate the source. It could just open the file, FILE-POSITION to the form, do a READ, then loop down the source path. Of course, it could read each form starting from the beginning, but that might be too slow.
Do XEPs really need Debug-Functions? The only time that we will commonly end up in the debugger on an XEP is when an argument type check fails. But I suppose it would be nice to be able to print the arguments passed...
Note that assembler-level code motion such as pipeline reorganization can cause problems with our PC maps. The assembler needs to know that debug info markers are different from real labels anyway, so I suppose it could inhibit motion across debug markers conditional on policy. It seems unworthwhile to remember the node for each individual instruction.
For tracing block-compiled calls: Info about return value passing locations? Info about where all the returns are?
We definitely need the return-value passing locations for debug-return. The question is what the interface should be. We don't really want to have a visible debug-function-return-locations operation, since there are various value passing conventions, and we want to paper over the differences.
Probably should be a compiler option to initialize stack frame to a special uninitialized object (some random immediate type). This would aid debugging, and would also help GC problems. For the latter reason especially, this should be locally-turn-onable (off of policy? the new debug-info quality?).
What about the interface between the evaluator and the debugger? (i.e. what happens on an error, etc.) Compiler error handling should be integrated with run-time error handling. Ideally the error messages should look the same. Practically, in some cases the run-time errors will have less information. But the error should look the same to the debugger (or at least similar).
;;;; Debugger interface:
How does the debugger interface to the "evaluator" (where the evaluator means all of native code, byte-code and interpreted IR1)? It seems that it would be much more straightforward to have a consistent user interface to debugging all code representations if there was a uniform debugger interface to the underlying stuff, and vice-versa.
Of course, some operations might not be supported by some representations, etc. For example, fine-control stepping might not be available in native code. In other cases, we might reduce an operation to the lowest common denominator, for example fetching lexical variables by string and admitting the possibility of ambiguous matches. [Actually, it would probably be a good idea to store the package if we are going to allow variables to be closed over.]
Some objects we would need: Location: The constant information about the place where a value is stored, everything but which particular frame it is in. Operations: location name, type, etc. location-value frame location (setf'able) monitor-location location function Function is called whenever location is set with the location, frame and old value. If active values aren't supported, then we dummy the effect using breakpoints, in which case the change won't be noticed until the end of the block (and intermediate changes will be lost.) debug info: All the debug information for a component. Frame: frame-changed-locations frame => location* Return a list of the locations in frame that were changed since the last time this function was called. Or something. This is for displaying interesting state changes at breakpoints. save-frame-state frame => frame-state restore-frame-state frame frame-state These operations allow the debugger to back up evaluation, modulo side-effects and non-local control transfers. This copies and restores all variables, temporaries, etc, local to the frame, and also the current PC and dynamic environment (current catch, etc.)
At the time of the save, the frame must be for the running function (not waiting for a call to return.) When we restore, the frame becomes current again, effectively exiting from any frames on top. (Of course, frame must not already be exited.)
Thread: Representation of which stack to use, etc. Block: What successors the block has, what calls there are in the block. (Don't need to know where calls are as long as we know called function, since can breakpoint at the function.) Whether code in this block is wildly out of order due to being the result of loop-invariant optimization, etc. Operations: block-successors block => code-location* block-forms block => (source-location code-location)* Return the corresponding source locations and code locations for all forms (and form fragments) in the block.
Variable maps:
There are about five things that the debugger might want to know about a variable:
Name Although a lexical variable's name is "really" a symbol (package and all), in practice it doesn't seem worthwhile to require all the symbols for local variable names to be retained. There is much less VM and GC overhead for a constant string than for a symbol. (Also it is useful to be able to access gensyms in the debugger, even though they are theoretically ineffable).
ID Which variable with the specified name is this? It is possible to have multiple variables with the same name in a given function. The ID is something that makes Name unique, probably a small integer. When variables aren't unique, we could make this be part of the name, e.g. "FOO#1", "FOO#2". But there are advantages to keeping this separate, since in many cases lifetime information can be used to disambiguate, making qualification unnecessary.
SC When unboxed representations are in use, we must have type information to properly read and write a location. We only need to know the SC for this, which would be amenable to a space-saving numeric encoding.
Location Simple: the offset in SC. [Actually, we need the save location too.]
Lifetime In what parts of the program does this variable hold a meaningful value? It seems prohibitive to record precise lifetime information, both in space and compiler effort, so we will have to settle for some sort of approximation.
The finest granularity at which it is easy to determine liveness is the the block: we can regard the variable lifetime as the set of blocks that the variable is live in. Of course, the variable may be dead (and thus contain meaningless garbage) during arbitrarily large portions of the block.
Note that this subsumes the notion of which function a variable belongs to. A given block is only in one function, so the function is implicit.
The variable map should represent this information space-efficiently and with adequate computational efficiency.
The SC and ID can be represented as small integers. Although the ID can in principle be arbitrarily large, it should be <100 in practice. The location can be represented by just the offset (a moderately small integer), since the SB is implicit in the SC.
The lifetime info can be represented either as a bit-vector indexed by block numbers, or by a list of block numbers. Which is more compact depends both on the size of the component and on the number of blocks the variable is live in. In the limit of large component size, the sparse representation will be more compact, but it isn't clear where this crossover occurs. Of course, it would be possible to use both representations, choosing the more compact one on a per-variable basis. Another interesting special case is when the variable is live in only one block: this may be common enough to be worth picking off, although it is probably rarer for named variables than for TNs in general.
If we dump the type, then a normal list-style type descriptor is fine: the space overhead is small, since the shareability is high.
We could probably save some space by cleverly representing the var-info as parallel vectors of different types, but this would be more painful in use. It seems better to just use a structure, encoding the unboxed fields in a fixnum. This way, we can pass around the structure in the debugger, perhaps even exporting it from the the low-level debugger interface.
[### We need the save location too. This probably means that we need two slots of bits, since we need the save offset and save SC. Actually, we could let the save SC be implied by the normal SC, since at least currently, we always choose the same save SC for a given SC. But even so, we probably can't fit all that stuff in one fixnum without squeezing a lot, so we might as well split and record both SCs.
In a localized packing scheme, we would have to dump a different var-info whenever either the main location or the save location changes. As a practical matter, the save location is less likely to change than the main location, and should never change without the main location changing.
One can conceive of localized packing schemes that do saving as a special case of localized packing. If we did this, then the concept of a save location might be eliminated, but this would require major changes in the IR2 representation for call and/or lifetime info. Probably we will want saving to continue to be somewhat magical.]
How about:
(defstruct var-info ;; ;; This variable's name. (symbol-name of the symbol) (name nil :type simple-string) ;; ;; The SC, ID and offset, encoded as bit-fields. (bits nil :type fixnum) ;; ;; The set of blocks this variable is live in. If a bit-vector, then it has ;; a 1 when indexed by the number of a block that it is live in. If an ;; I-vector, then it lists the live block numbers. If a fixnum, then that is ;; the number of the sole live block. (lifetime nil :type (or vector fixnum)) ;; ;; The variable's type, represented as list-style type descriptor. type)
Then the debug-info holds a simple-vector of all the var-info structures for that component. We might as well make it sorted alphabetically by name, so that we can binary-search to find the variable corresponding to a particular name.
We need to be able to translate PCs to block numbers. This can be done by an I-Vector in the component that contains the start location of each block. The block number is the index at which we find the correct PC range. This requires that we use an emit-order block numbering distinct from the IR2-Block-Number, but that isn't any big deal. This seems space-expensive, but it isn't too bad, since it would only be a fraction of the code size if the average block length is a few words or more.
An advantage of our per-block lifetime representation is that it directly supports keeping a variable in different locations when in different blocks, i.e. multi-location packing. We use a different var-info for each different packing, since the SC and offset are potentially different. The Name and ID are the same, representing the fact that it is the same variable. It is here that the ID is most significant, since the debugger could otherwise make same-name variables unique all by itself.
Stack parsing:
[### Probably not worth trying to make the stack parseable from the bottom up. There are too many complications when we start having variable sized stuff on the stack. It seems more profitable to work on making top-down parsing robust. Since we are now planning to wire the bottom-up linkage info, scanning from the bottom to find the top frame shouldn't be too inefficient, even when there was a runaway recursion. If we somehow jump into hyperspace, then the debugger may get confused, but we can debug this sort of low-level system lossage using ADB.]
There are currently three relevant context pointers: – The PC. The current PC is wired (implicit in the machine). A saved PC (RETURN-PC) may be anywhere in the current frame. – The current stack context (CONT). The current CONT is wired. A saved CONT (OLD-CONT) may be anywhere in the current frame. – The current code object (ENV). The current ENV is wired. When saved, this is extra-difficult to locate, since it is saved by the caller, and is thus at an unknown offset in OLD-CONT, rather than anywhere in the current frame.
We must have all of these to parse the stack.
With the proposed Debug-Function, we parse the stack (starting at the top) like this: 1] Use ENV to locate the current Debug-Info 2] Use the Debug-Info and PC to determine the current Debug-Function. 3] Use the Debug-Function to find the OLD-CONT and RETURN-PC. 4] Find the old ENV by searching up the stack for a saved code object containing the RETURN-PC. 5] Assign old ENV to ENV, OLD-CONT to CONT, RETURN-PC to PC and goto 1.
If we changed the function representation so that the code and environment were a single object, then the location of the old ENV would be simplified. But we still need to represent ENV as separate from PC, since interrupts and errors can happen when the current PC isn't positioned at a valid return PC.
It seems like it might be a good idea to save OLD-CONT, RETURN-PC and ENV at the beginning of the frame (before any stack arguments). Then we wouldn't have to search to locate ENV, and we also have a hope of parsing the stack even if it is damaged. As long as we can locate the start of some frame, we can trace the stack above that frame. We can recognize a probable frame start by scanning the stack for a code object (presumably a saved ENV).
Probably we want some fairly general mechanism for specifying that a TN should be considered to be live for the duration of a specified environment. It would be somewhat easier to specify that the TN is live for all time, but this would become very space-inefficient in large block compilations.
This mechanism could be quite useful for other debugger-related things. For example, when debuggability is important, we could make the TNs holding arguments live for the entire environment. This would guarantee that a backtrace would always get the right value (modulo setqs).
Note that in this context, "environment" means the Environment structure (one per non-let function). At least according to current plans, even when we do inter-routine register allocation, the different functions will have different environments: we just "equate" the environments. So the number of live per-environment TNs is bounded by the size of a "function", and doesn't blow up in block compilation.
The implementation is simple: per-environment TNs are flagged by the :Environment kind. :Environment TNs are treated the same as :Normal TNs by everyone except for lifetime/conflict analysis. An environment's TNs are also stashed in a list in the IR2-Environment structure. During during the conflict analysis post-pass, we look at each block's environment, and make all the environment's TNs always-live in that block.
We can implement the "fixed save location" concept needed for lazy frame creation by allocating the save TNs as wired TNs at IR2 conversion time. We would use the new "environment lifetime" concept to specify the lifetimes of the save locations. There isn't any run-time overhead if we never get around to using the save TNs. [Pack would also have to notice TNs with pre-allocated save TNs, packing the original TN in the stack location if its FSC is the stack.]
We want a standard (recognizable) format for an "escape" frame. We must make an escape frame whenever we start running another function without the current function getting a chance to save its registers. This may be due either to a truly asynchronous event such as a software interrupt, or due to an "escape" from a miscop. An escape frame marks a brief conversion to a callee-saves convention.
Whenever a miscop saves registers, it should make an escape frame. This ensures that the "current" register contents can always be located by the debugger. In this case, it may be desirable to be able to indicate that only partial saving has been done. For example, we don't want to have to save all the FP registers just so that we can use a couple extra general registers.
When when the debugger see an escape frame, it knows that register values are located in the escape frame's "register save" area, rather than in the normal save locations.
It would be nice if there was a better solution to this internal error concept. One problem is that it seems there is a substantial space penalty for emitting all that error code, especially now that we don't share error code between errors because we want to preserve the source context in the PC. But this probably isn't really all that bad when considered as a fraction of the code. For example, the check part of a type check is 12 bytes, whereas the error part is usually only 6. In this case, we could never reduce the space overhead for type checks by more than 1/3, thus the total code size reduction would be small. This will be made even less important when we do type check optimizations to reduce the number of type checks.
Probably we should stick to the same general internal error mechanism, but make it interact with the debugger better by allocating linkage registers and allowing proceedable errors. We could support shared error calls and non-proceedable errors when space is more important than debuggability, but this is probably more complexity than is worthwhile.
We jump or trap to a routine that saves the context (allocating at most the return PC register). We then encode the error and context in the code immediately following the jump/trap. (On the MIPS, the error code can be encoded in the trap itself.) The error arguments would be encoded as SC-offsets relative to the saved context. This could solve both the arg-trashing problem and save space, since we could encode the SC-offsets more tersely than the corresponding move instructions.